#include <stdio.h>
#include <time.h>
#include <assert.h>
#include "include/array_generator.h"
#include "include/array_help.h"

void sort(int arr[], int len) {
    for (int i = 0; i < len; i++) 
        for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--)
            Swap(arr + j, arr + j - 1, sizeof(int)); 
}

void sort2(int arr[], int len) {
    for (int i = 0; i < len; i++) {
        int elem = arr[i];  // 保存当前元素
        int j = i;          // j起始位置 
        for (; j > 0 && elem < arr[j - 1]; j--)
            arr[j] = arr[j - 1];// 覆盖，减少Swap动作
        arr[j] = elem;
    }
}


void sort2Generic(void* base, int len, int size, int (*compare)(void*, void*)) {
    for (int i = 0; i < len; i++) {
        for (int j = i; j > 0 && compare((char*)base + (j * size), (char*)base + ((j - 1) * size)) < 0; j--) {
            Swap((char*)base + (j * size), (char*)base + ((j - 1) * size), size);
        }
    }
}

int int_cmp(void* vp1, void* vp2) {
    return *(int*)vp1 - *(int*)vp2;
}

// 清晰， 确定， 可执行
// 循环不变量   函数定义，输入输出
int main(int argc, char *argv[]) {
    int len = 20000;
    int arr[len];
    GenRandomArray(arr, len, len); // 测试随机数组
    //GenOrderedArray(arr, len);        // 测试有序数组，插入排序在数据样本有序的时候，时间复杂度是O(n)
    // PrintIntArray(arr, len);
    time_t start = time(NULL);
    // sort2(arr, len);  
    sort2Generic(arr, len, sizeof(int), int_cmp); 
    time_t end = time(NULL); 
    printf("Time taken: %f seconds\n", difftime(end, start));
    // PrintIntArray(arr, len);
    return 0; 
}